package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;

/**
 * 扩展欧几里得算法与丢番图方程求解
 */
public class DiophantineEquation {

    /**
     * 扩展欧几里得算法返回结果封装
     */
    static class ExtendedEuclidResult {
        int x;      // 解x
        int y;      // 解y
        int gcd;    // 最大公约数gcd(a,b)

        ExtendedEuclidResult(int x, int y, int gcd) {
            this.x = x;
            this.y = y;
            this.gcd = gcd;
        }
    }

    /**
     * 扩展欧几里得算法：计算 ax + by = gcd(a,b)
     * @param a 方程系数1
     * @param b 方程系数2
     * @return 包含x、y、gcd的结果对象
     */
    private static ExtendedEuclidResult extendEuclid(int a, int b) {
        // 确保 a >= b，交换a、b并交换x、y的结果
        if (a < b) {
            ExtendedEuclidResult temp = extendEuclid(b, a);
            // 交换x和y，与C代码中交换指针逻辑一致
            return new ExtendedEuclidResult(temp.y, temp.x, temp.gcd);
        }

        // 存储 a//b 的系数列表（替代C的动态数组）
        List<Integer> coefficients = new ArrayList<>();

        // 循环计算系数，直到 b=0
        int originalA = a;
        int originalB = b;
        while (b != 0) {
            coefficients.add(a / b);
            int temp = b;
            b = a % b;
            a = temp;
        }

        // 初始化回代的x和y（对应C的 *x=1, *y=0）
        int x = 1;
        int y = 0;
        int gcd = a; // 最终a即为gcd(a,b)

        // 系数列表逆序回代（x, y = y, x - y*i）
        for (int i = coefficients.size() - 1; i >= 0; i--) {
            int coeff = coefficients.get(i);
            int newX = y;
            int newY = x - y * coeff;
            x = newX;
            y = newY;
        }

        return new ExtendedEuclidResult(x, y, gcd);
    }

    /**
     * 丢番图方程求解结果封装
     */
    static class DiophantineResult {
        int x0;  // x的特解
        int y0;  // y的特解
        int xk;  // x的通解系数（x = x0 + xk*t）
        int yk;  // y的通解系数（y = y0 + yk*t）

        DiophantineResult(int x0, int y0, int xk, int yk) {
            this.x0 = x0;
            this.y0 = y0;
            this.xk = xk;
            this.yk = yk;
        }
    }

    /**
     * 丢番图方程求解：ax + by = c
     * @param a 方程系数1
     * @param b 方程系数2
     * @param c 常数项
     * @return 包含特解和通解系数的结果对象
     * @throws IllegalArgumentException 方程无解时抛出
     */
    private static DiophantineResult diophantine(int a, int b, int c) {
        ExtendedEuclidResult eeResult = extendEuclid(a, b);
        int gcd = eeResult.gcd;

        // 检查是否有解：c必须是gcd(a,b)的倍数
        if (c % gcd != 0) {
            throw new IllegalArgumentException(
                    String.format("错误：方程无解（%d 不是 gcd(%d,%d)=%d 的倍数）", c, a, b, gcd)
            );
        }

        // 计算特解和通解系数
        int k = c / gcd;
        int x0 = eeResult.x * k;
        int y0 = eeResult.y * k;
        int xk = b / gcd;
        int yk = -a / gcd;

        return new DiophantineResult(x0, y0, xk, yk);
    }

    public static void main(String[] args) {
        // 测试用例：对应C代码的 diophantine(6, 9, 27)
        int a = 6, b = 9, c = 27;

        try {
            DiophantineResult result = diophantine(a, b, c);
            // 格式化输出（与C代码格式一致，处理正负号）
            String xkSign = result.xk > 0 ? " + " : " - ";
            int xkAbs = Math.abs(result.xk);
            String ykSign = result.yk > 0 ? " + " : " - ";
            int ykAbs = Math.abs(result.yk);

            System.out.printf("solution is x = %d%s%d t, y = %d%s%d t%n",
                    result.x0, xkSign, xkAbs,
                    result.y0, ykSign, ykAbs);
        } catch (IllegalArgumentException e) {
            System.err.println(e.getMessage());
            System.exit(1); // 无解，退出码1
        } catch (Exception e) {
            System.err.println("错误：未知异常！");
            e.printStackTrace();
            System.exit(2); // 其他错误，退出码2
        }
    }
}